public class Leet91 {
    /**
     * 一条包含字母 A-Z 的消息通过以下方式进行了编码：
     * <p>
     * 'A' -> 1
     * 'B' -> 2
     * ...
     * 'Z' -> 26
     * 给定一个只包含数字的非空字符串，请计算解码方法的总数。
     * 题目数据保证答案肯定是一个 32 位的整数。
     * 示例 1：
     * 输入：s = "12"
     * 输出：2
     * 解释：它可以解码为 "AB"（1 2）或者 "L"（12）。
     */
    public int numDecodings(String s) {
        if (s.charAt(0) == '0') {
            return 0;
        }
        int[] dp = new int[s.length() + 1];//长度为n时，的排列组合种类
        dp[0] = 1;
        dp[1] = 1;
        if (s.length() == 1) {
            return dp[1];
        }
        for (int i = 2; i <= s.length(); i++) {
            int num = Integer.parseInt(String.valueOf(s.charAt(i - 1)));

            int nums2 = Integer.parseInt(String.valueOf(s.charAt(i - 2)));

            if (nums2 + num == 0 || (num == 0 && nums2 > 2)) {
                return 0;
            } else if (num == 0 || nums2 == 0) {
                dp[i] = num == 0 ? dp[i - 2] : dp[i - 1];
            } else {
                dp[i] = nums2 * 10 + num > 26 ? dp[i - 1] : dp[i - 2] + dp[i - 1];
            }

        }
        return dp[s.length()];
    }
}
